\documentclass[a4paper,10pt]{article}

%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.96}

%configurações do fancy verbatim
\fvset{frame=single, xleftmargin=-80pt, xrightmargin=-80pt}
%configurações do listings
\lstset{frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, backgroundcolor=\color{claro}}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O compilador é o programa responsável por transformar um código-fonte de uma
linguagem de programação em outra linguagem, geralmente um código binário, ou
executável. O processo de compilação é feito através de várias etapas, como
mostrado na figura \ref{fig:fases}. 

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/fases.png} 
\label{fig:fases} 
\caption{Fases do processo de compilação} 
\end{figure}

Depois da geração de código pelo compilador, um interpretador é usado para
executar as instruções contidas neste código e finalmente realizar as tarefas
descritas no código-fonte feito pelo programador.

\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{imagens/interpretador.png}
\label{fig:interpretador}
\caption{Interpretador}
\end{figure}

Esta etapa da construção do compilador consiste na especificação e
implementação do gerador de código intermediário para
a máquina virtual Bós, que é uma adaptação da máquina MEPA. O interpretador
da linguagem Bós foi implementado no segundo trabalho prático.


\section{Análise Semântica}

A análise semântica é a terceira fase da compilação, onde se verificam os erros
de semântica no código fonte e se faz a coleta das informações necessárias para a
próxima fase da compilação, a geração de código objeto. O objeto da análise
semântica é trabalhar no nível de inter-relacionamento entre partes distintas do
programa.

A análise sintática verifica e aponta as expressões que quebram qualquer regra
determinada pela gramática. Mas o nível de complexidade aumenta quando tratamos
de linguagens dependentes de contexto. A análise semântica busca apontar (não
resolver) este tipo de erros (dependentes de contexto).

O objetivo da análise semântica é, assim, criar, a partir de um texto-fonte, uma
interpretação expressa em alguma notação adequada – geralmente uma linguagem
intermediária do compilador. Isto é feito com base nas informações das tabelas e nas
saídas dos outros analisadores.

A análise semântica utiliza-se da verificação de tipos para verificar se um
determinado operando recebe outro operando de mesmo tipo. Um exemplo comum
nas linguagens de programação é a análise semântica retornar um erro quando uma
variável do tipo numérica receber um valor tipo texto.

Um compilador usa uma tabela de símbolos para guardar informações sobre os
nomes declarados em um programa. A tabela de símbolos é pesquisada cada vez que
um nome é encontrado no programa conte. Alterações são feitas na tabela sempre
que um novo nome ou nova informação sobre um nome já existente é obtida. A
gerência da tabela de símbolos de um compilador deve ser implementada de forma a
permitir inserções e consultas de forma mais eficiente possível, além de permitir o
crescimento dinâmico da mesma. Cada entrada na tabela é a declaração de um nome.


\section{Tradução}

Tradução dirigida por sintaxe é uma técnica de especificação de compiladores
tradutores que permite associar ações semânticas às regras da gramática. Essa técnica
é utilizada em quase todos os compiladores modernos.

Nesta tradução do código de alto nível para o do processador está a associação
para traduzir para a linguagem-alvo, obtida para as diversas expressões do programa,
a representação da árvore gramatical.

Embora tal atividade possa ser realizada ao fim da análise sintática para toda
árvore, ela é realmente concluída com as ações semânticas, numa associação à
aplicação das regras de reconhecimento do analisador sintático.

Para se gerar o código, não é necessário ir diretamente para a linguagem
assembly do processador-alvo, pois o analisador sintático gera o mesmo com uma
linguagem próxima para uma máquina abstrata, isso independente de processadores
específicos. Depois esse código produzido traduz para a linguagem assembly desejada.
Ganha-se que grande parte do compilador é liberada para ser reaproveitada em
trabalhos de tipos de processadores dispares.

Na tradução dirigida pela sintaxe assume-se que os terminais tenham somente
atributos sintetizados quando as definições não apresentam nenhuma regra
semântica. Esses atributos são bastante usados na prática, onde uma sintaxe com os
mesmos é chamada de definição S-atribuída.

Em resumo:

\begin{itemize}
\item É uma tradução de linguagens guiada por gramáticas livres de contexto;
\item Faz uma amarração de atributos, que representam valores (tipo, endereço,
etc.), aos símbolos gramaticais de regras de produção, onde são representadas as
construções de linguagem;
\item Faz associação de regras semânticas às produções, a fim de realizar cálculos dos
valores de atributos amarrados.

\end{itemize}

Definições Dirigidas por Sintaxe são definições que usam uma gramática livre,
onde cada símbolo gramatical possui um conjunto associado de atributos. Os atributos
de símbolos podem ser sintetizados ou herdados. Nos do primeiro tipo o valor é
computado a partir dos valores dos atributos dos filhos do nó e, nos do segundo tipo, o
valor é computado a partir dos valores dos atributos do pai e dos irmãos do nó.

Normalmente a tradução do programa fonte no programa objeto é feita em dois
passos, e uma representação intermediária do programa fonte deve ser construída.
Tipicamente, essa representação intermediária assume uma de duas formas: uma
árvore (árvore sintática) ou uma sequência de comandos em uma linguagem
intermediária, cuja forma mais comum é a de quádruplas, ou seja, de comandos
compostos de um operador e de três operandos, que quase sempre são endereços.
Por exemplo, o comando de atribuição:

\colorbox{claro}{x := (a+b)*c}

A primeira árvore que se poderia usar como base para uma representação
intermediária é a árvore de derivação correspondente ao programa fonte, de acordo
com a gramática da linguagem fonte usada na construção do analisador sintático.
Entretanto, essa árvore de derivação em geral não é conveniente, uma vez que inclui
muitos detalhes desnecessários, que foram incluídos na sintaxe da linguagem fonte
para resolver problemas de ambiguidade, precedência, pontuação, clareza,
legibilidade, etc. Por esta razão, em alguns casos é conveniente a definição de uma
segunda sintaxe, chamada sintaxe abstrata, que ignora todos os aspectos não
essenciais da sintaxe original, conhecida como sintaxe concreta.

Tomando um compilador como um modelo de análise-e-síntese, podemos
considerar que seus módulos iniciais (front-end) traduzem um programa fonte em uma
representação intermediária, a partir da qual seus módulos finais (back-end) geram o
código objeto final. A geração de um código intermediário requer um passo a mais
para a tradução, tornando o processo um pouco mais lento. Embora um programa
fonte possa ser traduzido diretamente para a linguagem objeto, o uso de uma
representação intermediária, independente de máquina, tem a vantagem de ser
portável e de poder ser otimizado independentemente da plataforma. Os analisadores
léxico e sintático, juntamente com o analisador semântico, constituem o front-end do
compilador.

\section{Código de Três Endereços}

O código de três endereços é composto por uma sequência de instruções
envolvendo operações binárias ou unárias e uma atribuição. O nome ``três endereços''
está associado à especificação, em uma instrução, de no máximo três variáveis: duas
para os operadores binários e uma para o resultado. Assim, expressões envolvendo
diversas operações são decompostas nesse código em uma série de instruções,
eventualmente com a utilização de variáveis temporárias introduzidas na tradução.
Dessa forma, obtém-se um código mais próximo da estrutura da linguagem assembly
e, consequentemente, de mais fácil conversão para a linguagem-alvo.

Uma possível especificação de uma linguagem de três endereços envolve quatro
tipos básicos de instruções: expressões com atribuição, desvios, invocação de rotinas e
acesso indexado e indireto.

Instruções de atribuição são aquelas nas quais o resultado de uma operação é
armazenado na variável especificada à esquerda do operador de atribuição, aqui
denotado por :=. Há três formas para esse tipo de instrução. Na primeira, a variável
recebe o resultado de uma operação binária:
                
\colorbox{claro}{x := y op z}

O resultado pode ser também obtido a partir da aplicação de um operador
unário:

\colorbox{claro}{x := op y}

Na terceira forma, pode ocorrer uma simples cópia de valores de uma variável
para outra:
          
\colorbox{claro}{x := y}

Por exemplo, a expressão em C

\colorbox{claro}{a = b + c * d}

seria traduzida nesse formato para as instruções:

\colorbox{claro}{\_t1 := c * d}

\colorbox{claro}{a := b + \_t1}

As instruções de desvio podem assumir duas formas básicas. Uma instrução de
desvio incondicional tem o formato

\colorbox{claro}{goto L}

onde L é um rótulo simbólico que identifica uma linha do código. A outra forma
de desvio é o desvio condicional, com o formato
       
\colorbox{claro}{if x opr y goto L}

onde opr é um operador relacional de comparação e L é o rótulo da linha que
deve ser executada se o resultado da aplicação do operador relacional for verdadeiro;
caso contrário, a linha seguinte é executada.

Por exemplo, a seguinte iteração em C

\colorbox{claro}{while (i++ <= k)}

\colorbox{claro}{x[i] = 0;}

\colorbox{claro}{x[0] = 0;}

poderia ser traduzida para

\colorbox{claro}{\_L1: if i > k goto \_L2}

\colorbox{claro}{i := i + 1}

\colorbox{claro}{x[i] := 0}

\colorbox{claro}{goto \_L1}

\colorbox{claro}{\_L2: x[0] := 0}

A invocação de rotinas ocorre em duas etapas. Inicialmente, os argumentos do
procedimento são ``registrados'' com a instrução param; após a definição dos
argumentos, a instrução call completa a invocação da rotina. A instrução return indica
o fim de execução de uma rotina. Opcionalmente, esta instrução pode especificar um
valor de retorno, que pode ser atribuído na linguagem intermediária a uma variável
como resultado de call.

Por exemplo, considere a chamada de uma função f que recebe três argumentos
e retorna um valor:

\colorbox{claro}{f(a, b, c);}

Neste exemplo em C, esse valor de retorno não é utilizado. De qualquer modo, a
expressão acima seria traduzida para

\colorbox{claro}{param a}

\colorbox{claro}{param b}

\colorbox{claro}{param c}

\colorbox{claro}{\_t1 := call f,3}

onde o número após a vírgula indica o número de argumentos utilizados pelo
procedimento f. Com o uso desse argumento adicional é possível expressar sem
dificuldades as chamadas aninhadas de procedimentos.

O último tipo de instrução para códigos de três endereços refere-se aos modos
de endereçamento indexado e indireto. Para atribuições indexadas, as duas formas
básicas são

\colorbox{claro}{x := y[i]}

\colorbox{claro}{x[i] := y}

As atribuições associadas ao modo indireto permitem a manipulação de
endereços e seus conteúdos. As instruções em formato intermediário também utilizam
um formato próximo àquele da linguagem C:

\colorbox{claro}{x := \&y}

\colorbox{claro}{w := *x}

\colorbox{claro}{*x := z}

A representação interna das instruções em códigos de três endereços dá-se na
forma de armazenamento em tabelas com quatro ou três colunas. Na abordagem que
utiliza quádruplas (as tabelas com quatro colunas), cada instrução é representada por
uma linha na tabela com a especificação do operador, do primeiro argumento, do
segundo argumento e do resultado. Por exemplo, a tradução da expressão a=b+c*d;
resultaria no seguinte trecho da tabela:

\begin{center}
\begin{tabular}{| l | l | l | l |}
\hline
operador & arg1 & arg2 & resultado \\ \hline
* & c & d & \_t1 \\ \hline
+ & b & \_t1 & a \\ \hline
\end{tabular}
\end{center}

Para algumas instruções, como aquelas envolvendo operadores unários ou
desvio incondicional, algumas das colunas estariam vazias.

Na outra forma de representação, por triplas, evita a necessidade de manter
nomes de variáveis temporárias ao fazer referência às linhas da própria tabela no lugar
dos argumentos. Nesse caso, apenas três colunas são necessárias, uma vez que o
resultado está sempre implicitamente associado à linha da tabela. No mesmo exemplo
apresentado para a representação interna por quádruplas, a representação por triplas
seria:

\begin{center}
\begin{tabular}{| l | l | l |}
\hline
operador & arg1 & arg2 \\ \hline
* & c & d \\ \hline
+ & b & (1) \\ \hline
\end{tabular}
\end{center}

\section{Desenvolvimento}

Para implementar a análise léxica, utilizamos as ferramentais {\it lex} e {\it
yacc}. 
\subsection{Lex}

O programa Lex é um gerador de analisadores léxicos, através da definição de
expressões regulares para descrever padrões para os tokens. A notação de entrada
para a ferramenta {\it Lex} é chamada de {\it linguagem Lex}, e a ferramenta em
si é o {\it compilador Lex}. Internamente, o compilador Lex transforma os
padrões de entrada em m diagrama de transição e gera código em um arquivo
chamado lex.yy.c, que simula esse diagrama de transição.

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/lex.png} 
\label{fig:lex} 
\caption{Utilização do Lex} 
\end{figure}

Um programa Lex possui o seguinte formato:

\begin{Verbatim}
                declarações
                %%  
                regras de tradução
                %%
                funções auxiliares
\end{Verbatim}

A seção de declarações inclui declarações de variáveis, constantes manifestas e
definições regulares. Cada uma das regras de tradução possui o formato:

\begin{center}
Padrão \{ Ação \}
\end{center}

\subsection{Yacc}

Yacc é o gerador de analisador sintático utilizado neste trabalho. Um tradutor
pode ser construído usando o Yacc. Inicialmente, prepara-se um arquivo, digamos,
translate.y, contendo uma especificação Yacc dor tradutor. O comando do sistema
UNIX

\medskip
\colorbox{claro}{\$ yacc -d translate.y}
\medskip

transforma o arquivo translate.y em um programa C chamado y.tab.c, usando o
método LALR. O programa y.tab.c é uma representação de um analisador LALR
escrito em C, junto com outras rotinas C que o usuário pode ter preparado.
Compilando y.tab.c junto com a biblioteca ly que contém o programa de análise LR
usando o comando

\medskip
\colorbox{claro}{\$ cc y.tab.c -ly}
\medskip

obtemos o programa objeto desejado a.out, que realiza a tradução especificada
pelo programa Yacc original. Se outros procedimentos forem necessários, eles
podem ser compilados ou carregados com y.tab.c, assim como qualquer outro
programa em C.

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{imagens/yacc.png}
\label{fig:yacc}
\caption{Utilização do Yacc}
\end{figure}


Um programa fonte Yacc possui três partes:

\begin{Verbatim}
declarações
%%   
regras de tradução
%%
rotinas de suporte em C	
\end{Verbatim}


\pagebreak
\section{Gramática}

A gramática utilizada para realizar a análise sintática foi:

\VerbatimInput{../gramatica}


\section{Instruções para utilização}

Um arquivo de entrada, chamado lexemas.l, foi escrito na linguagem Lex e
descreve o analisador léxico a ser gerado. Através do comando:

\medskip
\colorbox{claro}{\$ lex lexemas.l} 
\medskip

o compilador Lex transforma lexemas.l em um programa C, e o armazena em um
arquivo que sempre se chama lex.yy.c.

Outro arquivo, chamado gramatica.y, foi escrito na linguagem Yacc e descreve a
gramática da linguagem. Usando o comando:

\medskip
\colorbox{claro}{\$ yacc -d gramatica.y}
\medskip

o Yacc transforma gramatica.y em um programa C, que é armazenado no arquivo
chamado y.tab.c.

 Esses dois arquivos são compilados pelo gcc
pelo comando:

\medskip
\colorbox{claro}{\$ gcc -o parser lex.yy.c y.tab.c}
\medskip
 
que gera o executável, que é o analisador sintático propriamente dito.

Para executar o programa utilizando como entrada o arquivo in.txt, por exemplo, usa-se o
comando:

\medskip
\colorbox{claro}{\$ ./parser $<$ in.txt}
\medskip

\section{Testes}

Abaixo está a saída do gerador de código pra diferentes construções da
linguagem.

\subsection{Teste 1}

Declaração de variáveis.

Entrada:
\VerbatimInput{../testes/teste1.in}

Saída:

\VerbatimInput{../testes/teste1.out}

\subsection{Teste 2}

Declaração de arranjos.

Entrada:
\VerbatimInput{../testes/teste2.in}

Saída:

\VerbatimInput{../testes/teste2.out}

\subsection{Teste 3}

Declaração de procedimentos.

Entrada:
\VerbatimInput{../testes/teste3.in}

Saída:

\VerbatimInput{../testes/teste3.out}


\clearpage
\section{Conclusão}
		
O desenvolvimento deste trabalho possibilitou o aprendizado acerca do
funcionamento de um analisador sintático. Pudemos aprender como funcionam as
ferramentas Lex e Yacc
e através delas fomos capazes de gerar o analisador sintático apropriado para a
linguagem SL. O desenvolvimento desse trabalho foi um passo muito importante para que o próximo trabalho seja
concluído, e que no final do curso um compilador seja implementado na íntegra.

\section{Código-fonte}

\subsection{lexemas.l}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../lexemas.l}

\subsection{gramatica.y}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../gramatica.y}

\subsection{symbol.c}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../symbol.c}

\subsection{inicia.c}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../inicia.c}

\subsection{offset.c}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../offset.c}

\subsection{gerador.c}

\lstinputlisting[xleftmargin=-80px,xrightmargin=-80px]{../gerador.c}

\clearpage
\begin{thebibliography}{99}
\bibitem{wiki} \url{en.wikipedia.org/wiki/Lex_(software)}
\bibitem{tut1} \url{http://dinosaur.compilertools.net/lex/index.html}
\bibitem{tut2} \url{http://ds9a.nl/lex-yacc/cvs/output/lexyacc.html}
\bibitem{tut3} \url{http://osr507doc.sco.com/en/tools/Lex_yacc.html}
\bibitem{mansic} \url{https://homepages.dcc.ufmg.br/~mariza/Cursos/CompiladoresI/Artigos/mansic.doc}
\bibitem{livro} Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, \emph{Compilers - Principles Techniques and Tools}, 2006
\end{thebibliography}

\end{document}
